package com.wanghlme.nowcoder;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wanghlme
 * @version 1.0
 */
public class NC_JZ35 {
    public static void main(String[] args) {

    }

    class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    public class Solution {
        RandomListNode Clone(RandomListNode pHead) {
            if (pHead == null) return pHead;
            Map<RandomListNode, RandomListNode> map = new HashMap<>();
            RandomListNode node = pHead;
            while (node != null) {
                RandomListNode clone = new RandomListNode(node.label);
                map.put(node, clone);
                node = node.next;
            }
            node = pHead;
            while (node != null) {
                map.get(node).next = map.get(node.next);
                map.get(node).random = map.get(node.random);
                node = node.next;
            }
            return map.get(pHead);
        }
    }
}
